package ordered_table

import (
	"fmt"
	"math/rand"
	"time"
)

// ######################  create new skip list node ############################
func NewSkipListNode(key CompareAble, value interface{}) *SkipListNode {
	return &SkipListNode{
		Key: key,
		Value: value,
		Next:  make([]*SkipListNode, 0),
	}
}

// ######################  skip list node struct  ############################
type SkipListNode struct {
	Key   CompareAble
	Value interface{}
	Next  []*SkipListNode
}

func (s *SkipListNode) isKeyLess(k CompareAble) bool {
	if k == nil {       // 当前节点与队尾节点的nil对比，需要当前节点为nil
		return true
	}
	if s.Key == nil {   // 自己本身的节点时初始节点，当为最小值
		return true
	}
	// 在多个节点中间时，需要进行比较
	return s.Key.CompareTo(k) < 0
}

func (s *SkipListNode) IsKeyEqual(k CompareAble) bool {
	if k == nil && s.Key == nil {
		return true
	}
	if k != nil && s.Key != nil {
		return s.Key.CompareTo(k) == 0
	}
	// 在多个节点中间时，需要进行比较
	return false
}

// ###################### create skip list node Map  ############################
func NewSkipListMap() *SkipListMap {
	head := NewSkipListNode(nil, "")
	head.Next = append(head.Next, nil)
	return &SkipListMap{
		Head: head,
		Size: 0,
		MaxLevel: 0,
	}
}

// ######################  skip list node Map  ############################
type SkipListMap struct {
	Head     *SkipListNode
	Size     int
	MaxLevel int
}

// 从第0层一层一层找下去
// 直到找到第0层小于key的最右节点
func (s *SkipListMap)MostRightLessNodeInTree(key CompareAble) *SkipListNode {
	if key == nil {
		return nil
	}
	curLevel := s.MaxLevel
	cur := s.Head
	for curLevel >= 0 {
		cur = s.MostRightLessNodeInLevel(key, cur, curLevel)
		curLevel--
	}
	return cur
}

// 在level层里，如何往右移动
// 现在来到的节点是cur，来到了cur的level层，在level层上，找到小于key最后一个节点并返回。
func (s *SkipListMap)MostRightLessNodeInLevel(key CompareAble, cur *SkipListNode, level int) *SkipListNode {
	next := cur.Next[level]
	for next != nil && next.isKeyLess(key) {
		cur = next
		next = cur.Next[level]
	}
	return cur
}

func (s *SkipListMap)ContainsKey(key CompareAble) bool {
	if key == nil {
		return false
	}
	less := s.MostRightLessNodeInTree(key)
	next := less.Next[0]
	return next.IsKeyEqual(key)
}

func (s *SkipListMap)Put(key CompareAble, value interface{}) {
	if key == nil { return }
	less := s.MostRightLessNodeInTree(key)
	find := less.Next[0]
	if find != nil && find.IsKeyEqual(key) {
		find.Value = value
	} else {
		s.Size++
		newNodeLevel := 0
		rand.Seed(time.Now().UnixNano())
		for rand.Intn(10) <= 4 {
			time.Sleep(time.Nanosecond)
			newNodeLevel++
		}
		for newNodeLevel > s.MaxLevel {
			s.Head.Next = append(s.Head.Next, nil)
			s.MaxLevel++
		}
		newNode := NewSkipListNode(key, value)
		for i:=0; i<= newNodeLevel; i++ {
			newNode.Next = append(newNode.Next, nil)
		}
		level := s.MaxLevel
		pre := s.Head
		for level >= 0 {
			pre = s.MostRightLessNodeInLevel(key, pre, level)
			if level <= newNodeLevel {
				newNode.Next[level] = pre.Next[level]
				pre.Next[level] = newNode
			}
			level--
		}
	}
}

func (s *SkipListMap)Get(key CompareAble) interface{} {
	if key == nil {return nil}
	less := s.MostRightLessNodeInTree(key)
	next := less.Next[0]
	if next.IsKeyEqual(key) {
		return next.Value
	}
	return nil
}

func (s *SkipListMap)Remove(key CompareAble) {
	if key == nil {return}
	if s.ContainsKey(key) {
		s.Size--
		level := s.MaxLevel
		pre := s.Head
		for level >= 0 {
			pre = s.MostRightLessNodeInLevel(key, pre, level)
			next := pre.Next[level]
			if next != nil && next.IsKeyEqual(key) {
				pre.Next[level] = next.Next[level]
			}
			// 根节点的层有可能下降
			if level != 0 && pre == s.Head && pre.Next[level] == nil {
				s.Head.Next = s.Head.Next[:level]
				s.MaxLevel--
			}
			level--
		}
	}
}

func (s *SkipListMap) CeilingKey(key CompareAble) CompareAble {
	less := s.MostRightLessNodeInTree(key)
	next := less.Next[0]
	if next != nil {return next.Key}
	return nil
}

func (s *SkipListMap) FloorKey(key CompareAble) CompareAble {
	less := s.MostRightLessNodeInTree(key)
	next := less.Next[0]
	if next.IsKeyEqual(key) {
		return next.Key
	}
	return less.Key
}

func (s *SkipListMap) GetSize() int {
	return s.Size
}

func (s *SkipListMap) PrintAll() {
	level := s.MaxLevel
	root := s.Head
	for level >= 0 {
		fmt.Printf("level %d :", level)
		s.PrintLevel(root, level)
		fmt.Println()
		level--
	}
}

func  (s *SkipListMap) PrintLevel(root *SkipListNode, level int) {
	cur := root.Next[level]
	for cur != nil {
		fmt.Print(cur.Key, " ")
		cur = cur.Next[level]
	}
}